1) Имеется Граф. Скажем классический пример про поездку из одного "города" в другой. Надо сравнить разные варианты проезда через промежуточные пункты. Но, хотелось бы на выходе иметь не "меньше километров - лучше", а "больше баллов - лучше". Какие сушествуют варианы перевода расстояния по графу в баллы (или как их еще можно назвать?)? Что-то я ничего подобного не нашел.

Можно конечно делить единицу на суммарное расстояние или придумать какую-нибудь более длинную формулу пересчета, но хотелось бы знать как это делается грамотно. Да еще и с несвязанными "городами" как быть? Пихать операторы if некрасиво как-то.

2) А теперь - уйдя от примера. Хотелось бы суммировать баллы, полученные для разных "путей".

3) Да еще в придачу хотелось бы, чтобы задав один и тот же "город" как ва качестве пункта отправления, так и назначения, получался высший балл. Т.е. чтобы система рассчитываемых баллов имела как начало (ноль например), так и конец (например единицу).

Извините, видимо написано сумбурно, но я впервые столкнулся с задачей о Графах.

Это сообщение отредактировал(а) _Y_ - 9.5.2007, 11:22

Не совсем въехал что тебе надо, но есть классический алгорит Дейкстры, который находит кратчайшее растояние от заданной вершинный ко всем остальным за время сравнимое с O(N^2) (в простейшем варианте). Алгоритм хорошо расписан на wikipedia.



Алгоритм Дейкстры. Википедия

У меня есть реализация в чистом виде на паскале.

Я так и предполагал, что выразил свою мысль нечетко. Только начинаю разбираться с проблемой.   Извиняюсь.

За ссылку на алгоритм большое спасибо. Очень поучительный   Сам же код, видимо, не нужен т.к. задача несколько другая. Попробую сформулировать иначе.

Имеется граф с узлами, скажем городами. Имеются "дороги" с расстояниями. Нужно определить что-то типа "дорожной близости городов друг от друга". Что-то вроде:

• Сам от себя город никак не отстоит. Следовательно показатель близости максимален. Скажем Score=1.
• Два города не связанные ни одной дорогой имеют минимальный показатель близости Score=0.
• Два города связанные дорогой, скажем в 100 км. 0 < Score(100 км) < 1
• Два города связанные дорогой, скажем в 100 км и еще дорогой через третий город (70 км + 50 км) Score(100 км) < Score(100 км, 70 км + 50 км)

При этом километры тоже не удобны т.к. они выражают степень удаленности, т.е. лучший показатель 0. Хотелось бы заменить их баллами, чтобы 0 показывал отсутствие дорог. Просто пользователям баллы будут понятнее поскольку речь в конце концов будет идти не о дорогах.

речь о том, что надо расстояние не минимизировать, а максимизировать? или просто вводить данные в другой форме?

skyboy, да нет, я вообще не собираюсь минимизировать или максимизировать. Я просто пытаюсь выразить свои мысли используя дороги в качестве примера. Но это у меня явно не получилось.  

Попробую сформулировать иначе. Имеются обьекты. Чем-то похожие, чем-то нет. Нужнен способ оценки их похожести. Шкала желательно, конечная. Вот картинка. Оценивается похожесть Object1 и Object2:

Что-то я картинки здесь не вижу  Вот ее URL http://www.sitey.narod.ru/4forums/net70510.gif

• В случае A обьекты совершенно непохожи. Следовательно, Score[A](1,2)=0
• Противоположный конец шкалы (Например, Score(1,1)=1) соответствует сравнению обьекта с самим собой или сравнению двух идентичных обьектов.
• Вариант B - обьекты имеют одинаковую площадь. Надо присвоить признаку "одинаковая площадь" какое-то количество баллов, чтобы 0<Score[B](1,2)<1. Возможен вариант с двумя или больше общими свойствами. Это тоже должно как-то учитываться.
• Вариант C - обьекты ничего одинакового не имеют, но каждый имеет что-то общее с третьим обьектом. Понятно, что чем длиннее цепочка - тем меньше конечный результат: 0<Score[C](1,2)<Score[C](1,3)<1 и 0<Score[C](2,3)<Score[C](1,3)<1. Но принцип присвоения баллов общим признакам должен оставатья общим.
• Вариант D.  Понятно, что 0<Score[B](1,2)<Score[D](1,2)<1 и 0<Score[C](1,2)<Score[D](1,2)<1.

Как задать систему баллов свойствам обьектов и как считать Score? Интересует как подойти к данной проблеме  

Это сообщение отредактировал(а) _Y_ - 10.5.2007, 12:10