Поиск кратчайшего пути между N-м числом точек на плоскости

[Shpuntik=)]

Здравствуйте.
Задачка такая:
Есть плоскость размером 30(абсцисс) на 15 (ординат).

Пользователь должен ввести координаты точек на этой плоскости.

Задача программы найти путь между начальной точкой (видимо это будет точка с самым малым иксом) до конечной точки (с самым большим значением икса).

Как объяснил препод я должен представить что это "деталь" и мы "сверлим" линию от начала детали(начальной точки) то конца(конечной точки).При этом вычислив оптимальный путь(минимальны от первой до последней точки).
Написать на любом языке программирования =)

Заранее спасибо =)

[Abstraction]

Задача программы найти путь между начальной точкой (видимо это будет точка с самым малым иксом) до конечной точки (с самым большим значением икса).

Так "видимо" или точно? Потому что без дополнительных уточнений это задача коммивояжёра в чистом виде.
Если же мы разрезаем деталь, то... разрез должен идти с постоянным неубыванием x? разрез не должен иметь самопересечений? ещё какое-то условие?

[Shpuntik=)]

Задача коммивояжёра для графов,которые уже имеют весы и т.п. атрибуты.


Деталь не то что бы "разрезается",в нем делается кривой вырез и хорошо замечено что от точки к точке Х должен возростать.Вы правы,самопересечений не должно быть.


З.Ы. Спасибо,что помогаете.

[Abstraction]

Задача коммивояжёра для графов,которые уже имеют весы и т.п. атрибуты.

В Вашем случае вес ребра - его длина.

Деталь не то что бы "разрезается",в нем делается кривой вырез

По ломаной? Или по более сложной кривой?

от точки к точке Х должен возрастать

Вероятно, всё же не убывать. Потому что иначе, если пара точек имеет одну и ту же x-координату, задача нерешаема. А так, можно разбить точки на классы с одинаковой x-координатой; каждый класс проходится от точки с минимальной y-координатой до точки с максимальной либо в обратном порядке; в каждый момент у нас есть минимальное возможное расстояние до "нижней" и "верхней" границы текущего класса.

А вообще, можете привести пример входных данных и ожидаемых выходных?

[Shpuntik=)]

Сообщение от Abstraction

.
А вообще, можете привести пример входных данных и ожидаемых выходных?

ДА

Вводим 6 точек
A(10.6) B(1.7) C(23.2) D(18.10) E(26.4) F(14.4)

в конечном итоге программа доодна выбрать точку B - началом.
Точку E - концом

Путь рассчитать по простой мат.формуле d = \/(х2— х1)^2 + (y2— y1)^2
и получить кратчайший путь : B-A-F-D-E (C-упускаем из результатов,т.к. самая ближеяя к D - E)
Как-то так

[Abstraction]

Тогда совсем непонятно. То есть, нужно пройти через подмножество точек? Что делать, если расстояния до пары точек в какой-то момент одинаковы? Вообще, что мешает тогда вести линию напрямую от "старта" до "финиша" - она явно будет кратчайшей? Нормально ли, что при подобном анализе "ближнего прицела" мы можем получить не самый короткий путь? (Если точки - (0,0), (8,8), (10,0), (10,10), (19,0) и (20,20), то мы упустим точки (8,8) и (10,10) и пройдём "углом", по длинному пути)

[Shpuntik=)]

Честно говоря,меня устроит программа,которая будет просто искать путь до ближайшей точки,но с бОльшим значением икса.Главное что бы получилась кривая от точки ближайшей к началу осей(х.у) до конечной,самой далней точки от начала отсчета.

[evg_m]

Вводим 6 точек
A(10.6) B(1.7) C(23.2) D(18.10) E(26.4) F(14.4)

сортируем по неубыванию нужной координаты
B(1.7) A(10.6) F(14.4) D(18.10) C(23.2) E(26.4)

и получить кратчайший путь : B-A-F-D-E (C-упускаем из результатов,т.к. самая ближеяя к D - E)

А почему?
DE =(26-18)^2 + (4-10)^2 =8^2 + 6^2 =64+36 =100
DC =(23-18)^2 + (2-10)^2 =5^2 + 8^2 =25+64 = 89

кратчайшим как уже заметили будем B - E
следующим пожалуй B - F - E (или В - А - E ?)
чем больше точек использовано, тем длинее путь. (точнее тем он не короче).

меня устроит программа,которая будет просто искать путь до ближайшей точки,но с бОльшим значением икса

сортируем по неубыванию нужной координаты
добавляем "расстояния" до всех последующих точек
анализируем и выбираем нужную нам следующую.

C-упускаем из результатов,т.к. самая ближеяя к D - E

[Shpuntik=)]

Все было бы прекрасно,знал бы хоть какой-то язык программирования=(
Я бы тут не сидел,алгоритм я и сам понимаю и составить могу.Написать программу - нет.