Да будет эта тема здесь. Вот нашел интересную библиотеку w32topl. Как понял она с графами работает. Ни кто с ней дело не имел? Может описание функций есть у кого? Вообще меня интересует все по графам.
классический учебник по теории графов: Оре (инициалы не помню) "Теория Графов" Ну, там инфы с избытком, а так на мат. порталах полно информации.
У меня тоже книжка есть, но другая. Но вот примера реализации там нет как раз. А с w32topl.dll никто дело не имел?
BreakPointMAN Увы, студенту не хватет ресурсов. Сейчас потихоньку разбираюсь с w32topl, но вот структура данных, организуемая одной из функций, и используемаю несколькими другими, мне не понятна. Та, под которую память выделяется ToplHeapCreate или нечто подобное.
Здравствуйте войны! Вот попросила девушка решить задачку. И как раз на графах. ТОлько вот я с ними дело раньше не имел. Чуток разобрался с ними... но пока в голове каша. Не могу привязать теорию именно к этой задаче. В общем вот: Задача по теме "поиск с возвратом. Задачи на графах". Дано множество из m n-мерных векторов. Удалить из него минимальное количество векторов так, чтобы среди оставшихся не было ортогональных(перпендикулярных, если кто не знает). Условие перпендикулярности есть. Только вот как, за что схватиться и как это привязать к графам... что то я не соображу... Как человеку, никогда не имевшему дело с теорией графов мне лезут в голову лишь алгоритмы которые с графами связать трудно)). Вобшем, подскажите логику решения.
pilat Значит думать будут другие, а благодарить девушка будет тебя? )) Я так понимаю, что из исходного набора надо каким-то образом построить граф, из которого потом будут выкидываться ребра и / или вершины по какому-то критерию. Я пока не совсем понимаю как это можно сделать, т.к. векторы у тебя n-мерные.
Насколько я понимаю, здесь дело не в n-мерности векторов. Положим, что векторы 3х-мерны, т.е. задаются в виде 2x + 3y + 4z - первый [1] 5x + 6y + 7z - второй [2] 8x + 9y + 10z - третий[3] ... Определить их ортогональность можно исходя из формулы произведения векторов. A*B = |A|*|B|*cos(A^B) (1) Вернее, cos(90град.) = A*B/|A|*|B| (2) Правую часть равенства (2)определяем исходя из координат вектора (например 2,3,4 - для первого вектора [1]). И если равенство (2) верно заключаем, что векторы ортогональны. Таким образом, я пологаю, мы сможем найти цепочки ортогональных векторов. Например, [1]<->[2], [3]<->[2] (<-> - означает ортогональность) если изобразить это визуально получиться такой граф: [1][2] .--. ф/ . [3] ф - пробел . - вершина графа (- и --) - ребра Так вот, по моему, суть задачи заключается в том, как проити по графу и удалить некоторые вершины таким образом, чтобы удалить вектор [2] и тем самым нарушить цепочку ортогональностей, а не векторы [1] и [2] или векторы [3] и [2]. Только вот моя проблема в том, что я не могу точно определить критерий удаления определенной вершины при большем количестве вершин и ребер.
pilat Берём в качестве узлов векторы и в качестве рёбер ортогональность(то есть если а и б ортогональны, то рисуем ребро а-б). Тогда поставленная задача эквивалентна так называемой maximum independent set problem. А та в свою очередь относится к классу NP (даже NP-hard), то есть решается только тупым перебором. Поправьте меня пожалуйста, если где напутал.
Это верно. Тогда я так понимаю, что перебор будет заключаться в нахождении вершин с максимальнам количеством ребер на данном этапе просмотра графа. И если это так, то является ли это истинно правильным решением задачи? Вот как я вижу решение ... К примеру: зашли мы по цепочке ортогональных векторов в самый конец(путем тупого перебора), тем самым выстроив эту цепочку(причем самую длинную). Т .е. последний вектор уже не ортогонален никакому, кроме предыдущего. Теперь я вижу только вариант идти назад и удалять векторы(вершины) через одну. Будет ли это решением задачи?
pilat Нигде не сказано, что такая цепочка вообще существует, с таким же успехом граф может быть цикличным. Не совсем понимаю твой способ, поэтому не могу ничего сказать. Самый простой способ - перебрать все 2<sup>n</sup> комбинации узлов и каждую проверять, является ли она "независимым множеством". Есть более быстрые алгоритмы, смотри например здесь ну или в google .
как я понимаю - это тактика. решением не является. как правильно было замечено, задача по природе является переборной (обратное не доказано . замечание: A*B = sum(A(i)*B(i)), i = 0..n-1, A(i) и B(i) - компоненты соответствующих векторов. короче, это скалярное произведение. если равно 0 - векторы ортогональны. так вот, план решения как я вижу. 0. строим матрицу скалярных произведений размерности m*m. на самом деле нужна её часть выше главной диагонали. и пусть i = 1. 1. каждую из m-i строк нашей половины матрицы можем удалить, таким образом получим m-i вариантов развития решения от данного этапа. да, удалить можем только строку, в которой есть нулевые элементы. так что m-i - верхняя оценка. получается дерево решений. узлы - этапы решения. листья дерева - ситуации, когда в нашей половинке матрицы нет нулевых элементов. в этой интерпртации задача сводится к нахождению самого короткого пути от вершины (начала решения) к листу. если на некотором этапе ты получил ситуацию, что не можешь удалить строку из матрицы - решил задачу. ответ - номера неудаленных строк. эти номера нужно хранить в отдельном массиве, соответствующем каждому узлу дерева решений. и удалять из него элементы при удалении строки
Artemy А можно по-подробнее, а то я въехать не могу. Сорри за тупость, просто я никогда дело с графами не имел.
