Нахождение минимальных пересечений

[leopatra]

Нахождение минимальных пересечений

помогите решить задачу, есть две параллельные линии (параллельные или нет это не столь важно), на первой линии точки A B C D E F..., на второй линии точки 1 2 3 4 5 ... они соеденены прямыми, например А-1 А-3 С-2 С-1, надо написать программу, которая находит минимальное пересечение этих прямых. Решение этой задачи вроди как должно быть в интернете, но я не могу найти, помогите пожалуйста, очень надо.

 

[Long Cat]

Какой язык и сроки?

 

[leopatra]

срок среда, язык всё равно какой, лучше Java, можно С.

 

[Long Cat]

Что понимается под минимальным пересечением? Вы пробовали решать самостоятельно?

 

[leopatra]

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

 

[leopatra]

Преподователь сказал также что эту задачу можно решать через матрицу, но это сложнее

 

[Long Cat]

Я пока плохо себе представляю, что требуется. Уточните, какие данные на входе.

 

[leopatra]

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

 

[Vladimir_S]

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

Уважаемый(-ая) Leopatra, ни в коей мере не намереваясь встревать в Ваш с LongCat диалог, я всё-таки позволю себе некоторые разъяснения того, чего, на мой взгляд, от Вас добиваются.
1. "Пересечение между линиями" не может быть ни минимальным, ни максимальным - оно либо есть, либо нет. Возможно, речь идет о минимальном количестве точек пересечения отрезков? Тогда так и надо писать.
2. Если так, то по какому алгоритму происходит соединение точек? Поясню. Если Вы соедините попарно точки
А - 1
B - 2
C - 3
и т.п., то никаких точек пересечения вообще не будет. Но, очевидно, так нельзя. А как можно? Со сколькими точками нижней горизонтальной прямой должна соединяться каждая точка верхней и наоборот? Чем это регламентируется? Каков алгоритм? Понимаете, пока Вы не проясните эти вопросы, толку всё равно не будет.

 

[leopatra]

Абсолютно правильно я имею ввиду минимальное количество точек пересечения, а насчёт алгоритма сама не поняла что предодователь имел ввиду, завтра постараюсь его найти и уточнить. Задание изначально не ясное было, просто я сделала предположение что есть классическая задача на это минимальное пересечение точек.

 

[Long Cat]

Я так подозреваю, что на входе еще есть количество прямых, которые нужно провести. Так вот, если таких прямых больше чем точек...

Да, с точки зрения математики, фраза "минимальное пересечение точек" - бредятина.

 

[leopatra]

вот что преподователь написал: Take in Internet "minimal crossing number" Wikipedia and you will find a full explanation

 

[leopatra]

это вообще кошмар какой-то... ничего не понятно...

 

[Long Cat]

Так я и думал - теория графов. Жаль, что у меня нет свободного времени, было бы интересно решить.

 

[leopatra]

Long Cat
сложно решается?

 

[Long Cat]

Сложно-понятие относительное. Если честно, мне как-то в лом в хорошую погоду тратить свое время за "спасибо".

 

[leopatra]

Long Cat
давай договоримся не за спасибо. во сколько ты свою работу оцениваешь?

 

[Long Cat]

Обращайтесь в ЛС или ICQ

 

[leopatra]

Long Cat
объясни как в лс писать, не могу найти

 

[Long Cat]

Если щелкнуть по моему профилю, выезжает меню, в меню есть пункт про ЛС. При этом ЛС должно быть включено в настройках приватности.