|
Действия ...
Новые сообщения [новые:0]
Дайджест
Горячие темы
Избранное [новые:0]
Форумы
Пользователи
Статистика
Статистика нагрузки
Мод. лог
Поиск
|
|
09.07.2009, 10:14:04
|
|||
|---|---|---|---|
Наименьшее расстояние |
|||
|
#18+
задача такая: Дано несколько точек на плоскости. нужно найти самый короткий путь наиболее удаленными проходя по другим. Какой алгоритм можете посоветовать? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
09.07.2009, 11:43:05
|
|||
|---|---|---|---|
|
|||
Наименьшее расстояние |
|||
|
#18+
aghasalim, Я так думаю: Определим расстояние между любыми двумя точками. Далее, выбираем ту пару, где расстояние максимальное, берем одну из точек. Отталкиваясь от этой (исходной) точки ищем ребро с минимальным весом (расстоянием до ближайшей точки) и т.д. пока не построим искомый путь / не придем в "конечную" точку... Следует учитывать, что найденный путь может "оставить" в стороне (изолировать) одну или несколько точек... :-( Вроде бы, если мне мой склероз не изменяет, алгоритм называется "построение максимального дерева с минимальным весом". ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
09.07.2009, 12:16:03
|
|||
|---|---|---|---|
|
|||
Наименьшее расстояние |
|||
|
#18+
aghasalimзадача такая: Дано несколько точек на плоскости. нужно найти самый короткий путь наиболее удаленными проходя по другим . Какой алгоритм можете посоветовать? Проходя по всем другим, или нет? Если да, то гугл ит "задача коммивояжера" (NP-полная, простых и быстрых решений не найдено). Если нет, то гугл ит "алгоритм Дейкстры". ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
09.07.2009, 12:16:52
|
|||
|---|---|---|---|
|
|||
Наименьшее расстояние |
|||
|
#18+
Перебрать все остовные деревья и выбрать из них нужное. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
13.07.2009, 10:24:22
|
|||
|---|---|---|---|
Наименьшее расстояние |
|||
|
#18+
Здесь таблица http://sinaq.az/. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
13.07.2009, 10:26:08
|
|||
|---|---|---|---|
Наименьшее расстояние |
|||
|
#18+
нужно пройти от S0 до Sw. при этом затратить минимум горючего (числы на таблице указывают на расход горючено). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
13.07.2009, 12:28:24
|
|||
|---|---|---|---|
Наименьшее расстояние |
|||
|
#18+
aghasalim, Если можно двигаться только вверх и вправо, то это простейший пример задачи на метод динамического программирования: задача о черепашке . Если можно двигаться также вниз и влево, то алгоритм Дейкстры . ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
start [/forum/topic.php?fid=16&tablet=1&tid=1344370]: |
0ms |
get settings: |
10ms |
get forum list: |
20ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
207ms |
get topic data: |
10ms |
get forum data: |
3ms |
get page messages: |
45ms |
get tp. blocked users: |
1ms |
| others: | 226ms |
| total: | 530ms |
| 0 / 0 |
