Find maximum clique with recursive function

8 次查看（过去 30 天）
hmhuang
hmhuang 2021-8-9
评论： breksam Amr 2021-9-12
I am solving an problem which has been stated and discussed here: maximum clique problem solve
As the OP showed in the above thread, the original version is inefficient because it is checking a bunch of sets of nodes that cannot possibly be part of a clique. So we need a smarter way to pick which nodes to check.
Therefore, based the tiny improvement in the accepted answer in maximum clique problem solve, I also tried:
  1. disregard nodes with length < length(clique)
  2. disregard nodes with the first element > clique(1)
  3. disregard nodes with the last element < clique(end)
  4. disregard nodes that are not in the follow list of first elemnt in the current clique
So my version of modification based on what @Jan wrote is changing line 15 to:
if ~any(node == clique) && length(graph{node}) >= length(clique) && graph{node}(1) <= clique(1) && graph{node}(end) >= clique(end) && any(node == graph{clique(1)})
Unfortunately, this runs for ~60 seconds on my computer, which is still not fast enough to pass the grader...
I also come up with the order of operands of && operator. So I change the above line to:
if any(node == graph{clique(1)}) && length(graph{node}) >= length(clique) && graph{node}(1) <= clique(1) && graph{node}(end) >= clique(end) && ~any(node == clique)
Although this gets a bit faster and runs for ~40 seconds on my computer, unfortunately this is still not fast enough to pass the grader...
I HOPE SOMEONE COULD PROVIDE SOME ADVICES.
ANY SUGGESTIONS WILL BE APPRECIATED.
  5 个评论
显示 3更早的评论
hmhuang
hmhuang 2021-8-10
编辑：hmhuang 2021-8-10
@Jan Thanks for asking. Yes, everyone can also follow themselves. The array was randomly generated. But to be qualified as an element of the clique, everyone should follow everyone else in the clique, following themselves isn't enough to be an element of a clique. For example, by the result: [ 1769 1773 1774 1833 2222 ], this means 1769 must follow 1773, 1774, 1833, 2222 and 1773 must follow 1769, 1774, 1833, 2222, and so on.
I hope this makes things more clear.

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

Jan
Jan 2021-8-12
编辑：Jan 2021-8-12
I've reduced the run time from 60 to 2 seconds using this method:
  • Convert the {1 x N} cell array of vectors to a [N x N] logical array X, which is true, if an ID in a specific column follows an ID in a specific row.
  • Omit elements of X if the corresponding elements of X.' are not true: A following cannot belong to a clique, if it points it is not mutual.
  • Run a loop over the rows (or columns - X is symmetric now). Select the sumbatrix:
v = X(k, :);
Y = X(v, v);
  • Convert this back to the original represantation using a cell vector and indices.
  • Call the original function as suggested in the other thread
An alternative description of the idea: I do not search the complete graph, but for the k'th ID only the elements of graph(graph{k}) are considered. The others cannot be part of a clique, which contains the k'th node of the graph.
I do not post the code, because this is a question of a course. A clean solution would stay at the representation as logical array to apply the recursive search. But my lazy method yields an acceleration of factor 30 already by a divide and conquer approach without touching the actual algorithm.
  7 个评论
显示 5更早的评论
Jan
Jan 2021-8-19
@Mehrail Nabil: Sorry, no. The question is part of a course. If a solution is found in the net, the homework question is not useful anymore.
I've explained a solution and hmhuang has mentioned, that you need to change one line of the original code only. Please read his last comment and find the solution by your own.
breksam Amr
breksam Amr 2021-9-12
@Mehrail Nabil did you find the answer i still don't understand it yet

请先登录，再进行评论。

更多回答（0 个）

类别

在 Help Center 和 File Exchange 中查找有关 Matrix Indexing 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by