Главная страница


ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Vitaly Slobodskoy                    2:5015/128.22  03 May 2002  21:48:53
 To : Arthur Martirosyan
 Subject : Re: Дейкстра
 -------------------------------------------------------------------------------- 
 
 До меня докатились слухи, что ты что-то там написал о "Дейкстра"! Так, так...
 надо бы разобраться...
 
  VS>> Пож-ста, вот решение этой задачи тем алгоритмом, который я приводил:
 
  VS>>      1  |  2      |  3       |  4        |  6          |
  VS>> -+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
  VS>> 2 |  2* |-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--- 
  VS>> 3 |  5  | 4(1-2)* |-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-- 
  VS>> 4 |  4  | 4(1)    | 4(1)*    |-+--+--+--+--+--+--+--+--+--+--+--+--- 
  VS>> 5 | oo  | 9(1-2)  | 8(1-2-3) | 8(1-2-3)  | 8(1-2-3)*   |-+--+--+--+- 
  VS>> 6 | oo  | oo      | 7(1-2-3) | 7(1-2-3)* |-+--+--+--+--+--+--+--+--- 
  VS>> 7 | oo  | oo      | oo       | oo        | 14(1-2-3-6) | 13(1-2-3-5)
 
  VS>> Вот, как бы и все! Так в чем проблема???
  AM> ОК! походу я немного прогнал, вернее делал не так.. все же пара вопросов
  AM> осталась, а именно: почему у нас сразу отпадает 4-я вершина, путь дальше
  AM> через нее не рассматривается, тогда, как 5-ю вершину мы рассматриваем до
  AM> конца и получаем таки через нее кратчайший путь, чем это определяется? по
  AM> логике все понятно, но как это обьяснять машине..
 
  Значит ты не уловил алгоритм. Рекомендую еще раз почитать мое письмо, в
 котором я довольно подробно рассказал об алгоритме. Hа каждом новом шаге
 (создавая новый столбец таблицы), мы выбираем из всех строк минимальное
 значение (на первом шаге это 2 у 2-ого пункта, на 2-ом шаге это 4 у 3-его
 пункта, на 3-ем шаге это 4 у 4-ого пункта и т.д.). Ту строку, в которой нашли,
 дальше не рассматриваем, это означает, что до пункта, соответствующего этой
 строке, кратчайший путь найден, далее для этого пункта рассматривать нет смысла
 - вычеркиваем ее (мысленно) и ставим эту новую вершину в заголовок нового
 столбца. Как формируется новый столбец, я уже рассказывал. Все строго по
 алгоритму - машине нужно только выбрать минимум и строить на новом шаге новый
 столбец!!
  Hадеюсь, что теперь понятно.
 
 Пока, Arthur..
                Vitaly Slobodskoy
 FIDO: 2:5015/128.22
 E-Mail: vital@mail.nnov.ru
 
 --- WP/95 Rel 1.78E (215.0) Reg.
  * Origin: ЭТО вам не ЭТО! Понятно! (ДМБ) (2:5015/128.22)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

 Тема:    Автор:    Дата:  
 Дейкстра   Arthur Martirosyan   14 Apr 2002 08:32:32 
 Дейкстра   Stanislav Shwartsman   19 Apr 2002 19:30:24 
 Дейкстра   Arthur Martirosyan   14 Apr 2002 11:25:58 
 Дейкстра   Stanislav Shwartsman   20 Apr 2002 18:21:22 
 Дейкстра   Arthur Martirosyan   14 Apr 2002 14:39:03 
 Дейкстра   Stanislav Shwartsman   21 Apr 2002 22:01:44 
 Дейкстра   Arthur Martirosyan   14 Apr 2002 17:52:47 
 Re: Дейкстра   Andrew Bogatyrev   23 Apr 2002 02:45:51 
 Дейкстра   Stanislav Shwartsman   23 Apr 2002 17:17:56 
 Re: Дейкстра   Andrew Bogatyrev   24 Apr 2002 02:18:05 
 Дейкстра   Arthur Martirosyan   14 Apr 2002 19:10:53 
 Дейкстра   Andrey Dashkovsky   20 Apr 2002 17:18:10 
 Дейкстра   Arthur Martirosyan   14 Apr 2002 14:42:07 
 Re: Дейкстра   Vitaly Slobodskoy   20 Apr 2002 23:12:33 
 Дейкстра   Stanislav Shwartsman   22 Apr 2002 08:01:35 
 Re: Дейкстра   Vitaly Slobodskoy   23 Apr 2002 22:06:15 
 Дейкстра   Arthur Martirosyan   14 Apr 2002 19:39:25 
 Re: Дейкстра   Vitaly Slobodskoy   26 Apr 2002 15:56:11 
 Дейкстра   Arthur Martirosyan   26 Apr 2002 10:20:02 
 Re: Дейкстра   Vitaly Slobodskoy   02 May 2002 21:43:52 
 Дейкстра   Arthur Martirosyan   01 May 2002 15:34:48 
 Re: Дейкстра   Vitaly Slobodskoy   03 May 2002 21:48:53 
 Дейкстра   Arthur Martirosyan   04 May 2002 09:46:14 
 Re: Дейкстра   Dmitry Volkov   03 May 2002 21:11:36 
 Дейкстра   Arthur Martirosyan   04 May 2002 09:36:53 
Архивное /ru.algorithms/39086c104b87.html, оценка 1 из 5, голосов 10
Яндекс.Метрика
Valid HTML 4.01 Transitional