Здравствуйте!
Вот попросила девушка решить задачку.ТОлько вот я с ними дело раньше не имел. Чуток разобрался с ними... но пока в голове каша. Не могу привязать теорию именно к этой задаче. В общем вот:

Задача по теме "поиск с возвратом. Задачи на графах".
Дано множество из m n-мерных векторов. Удалить из него минимальное количество векторов так, чтобы среди оставшихся не было ортогональных(перпендикулярных, если кто не знает).

Условие перпендикулярности есть. Только вот как, за что схватиться и как это привязать к графам... что то я не соображу... Как человеку, никогда не имевшему дело с теорией графов мне лезут в голову лишь алгоритмы которые с графами связать трудно)).
Вобшем, подскажите логику решения, а лучше намек алгоритмом))

Здравствуйте, i.pilat, Вы писали:

IP>Здравствуйте!
IP>Вот попросила девушка решить задачку.ТОлько вот я с ними дело раньше не имел. Чуток разобрался с ними... но пока в голове каша. Не могу привязать теорию именно к этой задаче. В общем вот:

IP>Задача по теме "поиск с возвратом. Задачи на графах".
IP>Дано множество из m n-мерных векторов. Удалить из него минимальное количество векторов так, чтобы среди оставшихся не было ортогональных(перпендикулярных, если кто не знает).

IP>Условие перпендикулярности есть. Только вот как, за что схватиться и как это привязать к графам... что то я не соображу... Как человеку, никогда не имевшему дело с теорией графов мне лезут в голову лишь алгоритмы которые с графами связать трудно)).
IP>Вобшем, подскажите логику решения, а лучше намек алгоритмом))

Строим неориентированный граф, вершины которого будут соответствовать векторам, а ребро между вершинами (i,j) будет существовать, если соответсвующие вектора ортогональны. Далее получаем задачу о нахождении максимального независимого подмножества
http://mathworld.wolfram.com/MaximalIndependentVertexSet.html
либо эквивалентную ей задачу о нахождении максимальной клики в графе, множество ребер которого является дополнением множества ребер первой задачи
http://mathworld.wolfram.com/Clique.html
http://en.wikipedia.org/wiki/Clique_problem

Здравствуйте, i.pilat, Вы писали:

IP>Задача по теме "поиск с возвратом. Задачи на графах".
IP>Дано множество из m n-мерных векторов. Удалить из него минимальное количество векторов так, чтобы среди оставшихся не было ортогональных(перпендикулярных, если кто не знает).

Если построить граф, где вершины — вектора, а между двумя вершинами есть ребро, если соответствующие вектора ортогональны, то исходная задача будет сведена к поиску минимального вершинного покрытия для данного графа. Эта задача является NP-полной, насколько я знаю.

Здравствуйте, Vintik_69, Вы писали:

V_>Здравствуйте, i.pilat, Вы писали:

IP>>Задача по теме "поиск с возвратом. Задачи на графах".
IP>>Дано множество из m n-мерных векторов. Удалить из него минимальное количество векторов так, чтобы среди оставшихся не было ортогональных(перпендикулярных, если кто не знает).

V_>Если построить граф, где вершины — вектора, а между двумя вершинами есть ребро, если соответствующие вектора ортогональны, то исходная задача будет сведена к поиску минимального вершинного покрытия для данного графа. Эта задача является NP-полной, насколько я знаю.
Вот и возникает вопрос причем тут графы.

Итак,
V -- исходное множество векторов.
W -- линейное многообразие V, то есть линейная комбинация векторов из множества V (заранее извиняюсь, если я напутал с терминами).
Размер базиса W (число ортоганальных векторов, линейная комбинация которых равна W) не зависит от входящих в него векторов. Таким образом нужно просто найти все ортогональные вектора, а все остальные и будут тем минимальным количеством векторов. Зачем здесь графы я не понимаю, но если у нас вершины графа -- это вектора, а ребра означают ортоганальность векторов, то получается что нужно просто найти все смежные вершины для какой то одной. Все не смежные нужно удалить.

Здравствуйте, CiViLiS, Вы писали:

CVL>Итак,
CVL>V -- исходное множество векторов.
CVL>W -- линейное многообразие V, то есть линейная комбинация векторов из множества V (заранее извиняюсь, если я напутал с терминами).
CVL>Размер базиса W (число ортоганальных векторов, линейная комбинация которых равна W) не зависит от входящих в него векторов. Таким образом нужно просто найти все ортогональные вектора, а все остальные и будут тем минимальным количеством векторов.

Вектора:
(1,0,0)
(0,1,0)
(1,0,1)

Как будешь искать все ортогональные и какой ответ получится?

Здравствуйте, _DAle_, Вы писали:

_DA>Здравствуйте, CiViLiS, Вы писали:

_DA>Как будешь искать все ортогональные и какой ответ получится?
упс задание не правлиьно прочитал.. я подумал что надо найти базис, то есть чтобы не было НЕ ортоганальных.