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


ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Arthur Martirosyan                   2:5061/103.51  01 May 2002  15:34:48
 To : Vitaly Slobodskoy
 Subject : Дейкстра
 -------------------------------------------------------------------------------- 
 
 
  Четверг Май 02 2002 21:43 You wrote:
 
  AM>> |   1   2   3   4   5   6   7
  AM>> -|-+--+--+--+--+--+--+--+--+---
  AM>> 1|  oo   2   5   4  oo  oo  oo  |
  AM>> 2|   2  oo   2  oo   7  oo  oo  |
  AM>> 3|   5   2  oo   1   4   3  oo  |
  AM>> 4|   4  oo   1  oo  oo   4  oo  |
  AM>> 5|  oo   7   4  oo  oo   5   5  |
  AM>> 6|  oo  oo   3   4   5  oo   7  |
  AM>> 7|  oo  oo  oo  oo   5   7  oo  |
 
  AM>> Это простой пример, который я просто еру за основу.. Опять же,
  AM>> встречаются и вообще тупиковые ситуации, когда придется двигаться
  AM>> обратно..
 
  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>  В скобках указана история. В принципе, это не предусматривается
  VS> алгоритмом, т.к. его задача - это - минимальное расстояние, но,
  VS> согласись, хранить ее не сложно. Итак, мы имеем такие кратчайшие пути
  VS> из пункта 1 во все остальные: в пункт 2: 1->2 (длина 2) в пункт 3:
  1->2->> 3 (длина 4) в пункт 4: 1->4 (длина 4) в пункт 5: 1->2->3->5
  VS> (длина 8) в пункт 6: 1->2->3->6 (длина 7) в пункт 7: 1->2->3->5->7
  VS> (длина 13)
 
  VS>  Вот, как бы и все! Так в чем проблема???
 
 ОК! походу я немного прогнал, вернее делал не так.. все же пара вопросов
 осталась, а именно: почему у нас сразу отпадает 4-я вершина, путь дальше через
 нее не рассматривается, тогда, как 5-ю вершину мы рассматриваем до конца и
 получаем таки через нее кратчайший путь, чем это определяется? по логике все
 понятно, но как это обьяснять машине..
 ... OK!____________________________________________________________________
 --- Желаю удачи и всего хорошего, Arthur M. -------------------------------
  * Origin: A dream comes true (2:5061/103.51
 
 

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

 Тема:    Автор:    Дата:  
 Дейкстра   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/239273cd00cac.html, оценка 2 из 5, голосов 10
Яндекс.Метрика
Valid HTML 4.01 Transitional