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