|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Ilya Rogov 2:5030/1334.1024 11 Jan 2003 02:43:28
To : Stanislav Shwartsman
Subject : коммивояжёр
--------------------------------------------------------------------------------
Давным-давно, 10 Jan 03 09:07, когда земля была ещё тёпленькая
и по ней бегали мамонты, Stanislav Shwartsman и Ilya Rogov говорили про
коммивояжёр:
IR>> Кто-нибудь слышал о HЕРЕКУРСИВHОМ решении задачи сабжа ? Я
IR>> подчёркиваю - HЕРЕКУРСИВHОМ. Ведь всякую рекурсивный алгоритм
IR>> можно преобразовать в аналогичный итерационный. Или я не прав ?
SS> В связи с тем, что сабж задача NP-полная, искать ее оптимальное
SS> решение даже "почти полным перебором" уже практически бессмысленно.
SS> Для решения таких задач используются приближенные алгоритмы, которые
SS> вместо "почти полного перебора" предлагают "почти оптимальное
SS> решение" зато за приемлемое время. И вот они-то как раз чаще всего HЕ
SS> рекурсивны :)
Дело в том, что я хочу проверить работу как раз именно такого алгоритма. Я
ведь не буду на глазик считать наикратчайший путь в графе даже из 5 вершин. А
хочется проверить, скажем для 10-15. Время пока есть, посижу часик перед
монитором, потерплю ...
Ilya Rogov
... Бредить помогали вопли моих соседей
---
* Origin: Когда Бог делал время - он сделал его достаточно (2:5030/1334.1024)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
коммивояжёр 
