Finden einer Vektorsumme in einer Matrix

WICHTIG: Der Betrieb von goMatlab.de wird privat finanziert fortgesetzt. - Mehr Infos...

Partner:

Forum

Option

[Erweitert]

• Diese Seite per Mail weiterempfehlen

Gehe zu:

ripper1986

Forum-Anfänger


	Beiträge: 14

	Anmeldedatum: 05.02.13

	Wohnort: ---

	Version: ---

Verfasst am: 05.02.2013, 21:29 Titel: Finden einer Vektorsumme in einer Matrix

Hallo zusammen, ich habe ein bisschen in den Foren gestöbert und leider hat das mein Problem nicht gelöst... ich stehe irgendwie auf dem Schlauch... ich komme mal zu meinem Problem... ich möchte eine Funktion schreiben in die eine Matrix eingegeben wird. Es handelt sich um eine nxn-Matrix, deren Einträge nur aus Einsen und Nullen. Die Spalten betrachte ich nun als Vektoren. Ich möchte nun eine minimale Anzahl an Vektoren bestimmen, so dass die Summe dieser Vektoren in JEDER KOMPONENTE echt größer als Null ist. Falls dies nicht möglich ist, soll einfach eine Null ausgegeben werden. Bislang habe ich lediglich, dass dies für eine Spalte gilt. Ich stehe total auf dem Schlauch und kann das gerade irgendwie nicht umsetzen... wäre super wenn mir jemand helfen könnte... hier erstmal das was ich bereits habe:

Code:

function [ausgabe] = dominatingSet(A)

ausgabe = 0
[dim1 dim2] = size(A);
einsen(1:dim1)=1;
einsen = einsen';

for i=1:1:dim1
if A(:,i)>0==einsen
ausgabe = i;
break
end
end
end

Funktion ohne Link?

Beste Grüße aus dem Ruhrgebiet,
Daniel

[EDITED, Jan, Bitte Code-Umgebung benutzen - danke!]

Jan S

Moderator


	Beiträge: 11.057

	Anmeldedatum: 08.07.10

	Wohnort: Heidelberg

	Version: 2009a, 2016b

Verfasst am: 06.02.2013, 09:58 Titel: Re: Finden einer Vektorsumme in einer Matrix

Hallo Daniel,

Zitat:

Ich möchte nun eine minimale Anzahl an Vektoren bestimmen, so dass die Summe dieser Vektoren in JEDER KOMPONENTE echt größer als Null ist.

Das verstehe ich noch nicht ganz. Ich rate mal:

Code:

function ausgabe = dominatingSet(A)
B = cumsum(A, 2);
c = all(B, 1);
ausgabe = find(c, 1);
if isempty(ausgabe)
ausgabe = 0;
end

Funktion ohne Link?

Oder equivalent:

Code:

function ausgabe = dominatingSet(A)
ausgabe = 0;
c = 0;
k = 0;
while ausgabe = 0
k = k + 1;
c = or(c, A(:, k));
if all(c)
ausgabe = k;
end
end

Funktion ohne Link?

Passt das zu Deinem Problem?

Gruß, Jan

ripper1986

Themenstarter

Forum-Anfänger


	Beiträge: 14

	Anmeldedatum: 05.02.13

	Wohnort: ---

	Version: ---

Verfasst am: 06.02.2013, 10:14 Titel:

Hallo Jan,

leider nicht, ich versuche nochmal mein Problem genauer zu beschreiben. Es wird eine Matrix gegeben, die mit Einsen und Nullen gefüllt ist. Eine Spalte in der Matrix fasse ich nun als Vektor auf. Da es sich um eine Matrix handelt deren Dimension beliebig ist (sie ist aber quadratisch), nehme ich an, dass es eine nxn-Matrix ist. Jede Spalte in dieser Matrix fasse ich nun als Vektor auf. Ich habe also n Vektoren, die ich betrachte. Diese nummeriere ich von links nach rechts mit den Zahlen 1,2,...,n durch.
Soviel zum "Hintergrund". Nun suche ich eine MINNIMALE Menge dieser n Vektoren, deren Summe in jeder Komponente echt größer als Null ist. Es ist klar, dass das unter Umständen ein Vektor sein kann, wenn er in allein Einträgen eine Eins hat. Es kann aber auch sein, dass wir alle n Vektoren benötigen. Das wäre zB der Fall wenn es sich um eine Diagonalmatrix handelt.

Am besten wäre es, wenn die Ausgabe ein Vektor wäre, in dem die Vektoren eingetragen sind, die man benötigt. Dass die Lösung nicht eindeutig ist, ist klar, in diesem Falle aber egal.

Ich hoffe ich habe es jetzt so beschrieben, dass man es verstehen kann Wink

. Wie ich es mache, wenn ich nur einen Vektor benötige, ist klar, ich komme allerdings mit der Verschachtelung nicht so ganz klar Very Happy

Harald

Forum-Meister


	Beiträge: 24.501

	Anmeldedatum: 26.03.09

	Wohnort: Nähe München

	Version: ab 2017b

Verfasst am: 06.02.2013, 10:23 Titel:

Hallo,

das ist letztlich ein Optimierungsproblem.
Wie groß ist n typischerweise?

Grüße,
Harald

ripper1986

Themenstarter

Forum-Anfänger


	Beiträge: 14

	Anmeldedatum: 05.02.13

	Wohnort: ---

	Version: ---

Verfasst am: 06.02.2013, 10:25 Titel:

Das ist schwer zu sagen, wir können einfach mal 100 annehmen, interessant ist es aber für alle n die größer als 5 sind.

Harald

Forum-Meister


	Beiträge: 24.501

	Anmeldedatum: 26.03.09

	Wohnort: Nähe München

	Version: ab 2017b

Verfasst am: 06.02.2013, 10:43 Titel:

Hallo,

die Frage des n ist sehr wichtig. Für n bis zu ca. 20 dürfte es am einfachsten sein, die 2^20 Kombinationen (evtl. mit gewissen Vereinfachungen) durchzuprobieren. Für n über 30 dürfte das zu zeitaufwändig sein.
Bei solchen größeren n würde ich zu genetischen Algorithmen (ga) tendieren. Natürlich kannst du dir auch händisch einen speziell für diese Problematik gedachten Optimierungsalgorithmus basteln.
Was ich in jedem Fall machen würde: basierend auf der dahinterstehenden Anwendung schauen, ob es da spezialisierte Algorithmen gibt.

Grüße,
Harald

ripper1986

Themenstarter

Forum-Anfänger


	Beiträge: 14

	Anmeldedatum: 05.02.13

	Wohnort: ---

	Version: ---

Verfasst am: 06.02.2013, 10:50 Titel:

Um ehrlich zu sein, wäre ich mit dem Algorithmus, der alles einfach durchhgeht schon recht zufrieden! Genau das habe ich versucht und bekomme es einfach nicht hin es zu verschachteln. Der Zeitaufwand spielt in diesem Falle (für mich) eine untergeordnete Rolle.
Da es nur ein kleiner Nebenbereich von dem ist an dem ich gerade arbeite und ich noch nie was von genetischen Algorithmen gehört habe, würde ich mich erstmal mit "trial and error" zufriedengeben Very Happy

ripper1986

Themenstarter

Forum-Anfänger


	Beiträge: 14

	Anmeldedatum: 05.02.13

	Wohnort: ---

	Version: ---

Verfasst am: 06.02.2013, 11:25 Titel:

Okay, ich sehe ein, dass die Frage irgendwo überflüssig war Smile

. Trail and error habe ich jetzt mehr oder weniger hinbekommen...!! Wenn ich am ende noch Zeit haben sollte werde ich mich mal in genetische Algorithmen einlesen!! Vielen Dank für die schnellen Antworten und die Hilfe Smile

Besten Gruß aus dem verschneiten Ruhrgebiet!!

Harald

Forum-Meister


	Beiträge: 24.501

	Anmeldedatum: 26.03.09

	Wohnort: Nähe München

	Version: ab 2017b

Verfasst am: 06.02.2013, 16:22 Titel:

Hallo,

mir ist gerade klar geworden, dass man vor ga wahrscheinlich bintprog versuchen sollte.

Grüße,
Harald

ripper1986

Themenstarter

Forum-Anfänger


	Beiträge: 14

	Anmeldedatum: 05.02.13

	Wohnort: ---

	Version: ---

Verfasst am: 10.02.2013, 16:30 Titel:

Hallo zusammen,

ich habe es jetzt soweit hinbekommen. Da der Code in meinen Augen aber viel zu lang ist wollte ich euch mal fragen ob ihr eine Möglichkeit seht, ihn zu verkürzen. Im Prinzip kommt in jedem Schritt eine Schleife hinzu und in den Vektor wird ein Element mehr hineingeschrieben! Ich bekomme es leider nicht hin, das mit einer Schleife zu bauen, die es automatisch immer "erweitert". Die Funktion SUMME addiert die Vektoren, die in b gelistet sind. Hier mal ein Teil des Codes:

Code:

function [ ] = dS(A)

[dim1, x] = size(A);

for i=1:dim1
einsen(:,i)=1;
end

for i=1:dim1
b= [i];
if Summe(A,b) >= einsen
disp('Ergebnis')
disp(b)
return
end
end

for i=1:dim1
for j=i+1:dim1;
b= [i j];
if Summe(A,b) >= einsen
disp('Ergebnis')
disp(b)
return
end
end
end
for i=1:dim1
for j=i+1:dim1;
for k=j+1:dim1
b= [i j k];
if Summe(A,b) >= einsen
disp('Ergebnis')
disp(b)
return
end
end
end
end

usw....

Funktion ohne Link?

Besten Gruß

Jan S

Moderator


	Beiträge: 11.057

	Anmeldedatum: 08.07.10

	Wohnort: Heidelberg

	Version: 2009a, 2016b

Verfasst am: 10.02.2013, 18:25 Titel:

Hallo ripper1986,

Ich verstehe nicht, wozu Du den Vektor "einsen" benötigst. Eine Skalar 1 würde doch reichen, oder? Falls Du doch einen Vektor benötigst, wäre dies effizienter als die Schleife:

Code:

einsen = ones(1, dim1);

Funktion ohne Link?

Wenn ich es richtig verstehe, berechnet "Summe(A, b)" dies;

Code:

sum(A(b, :))

Funktion ohne Link?

Dann könnte man aber auch die ganze Schlefe weglassen:

Code:

S = sum(A, 2);
Index = (S >= 1);
disp('Ergebnis:');
disp(Index);

Funktion ohne Link?

Gruß, Jan

ripper1986

Themenstarter

Forum-Anfänger


	Beiträge: 14

	Anmeldedatum: 05.02.13

	Wohnort: ---

	Version: ---

Verfasst am: 10.02.2013, 18:39 Titel:

Hallo Jan,

also die ersten beiden Einwände... da muss ich dir Recht geben, so ist es wesentlich einfacher. Der dritte Teil ist mir allerdings nicht wirklich klar. Das Problem ist, dass ich "alle Möglichen" (b hat 1 oder 2 oder... oder 10 Einträge) Kombinationen durch gehen möchte. Mir ist nicht klar was du meinst.

Besten Gruß

Harald

Forum-Meister


	Beiträge: 24.501

	Anmeldedatum: 26.03.09

	Wohnort: Nähe München

	Version: ab 2017b

Verfasst am: 10.02.2013, 20:50 Titel:

Hallo,

mit bitget kannst du dir schön Sequenzen von 0 und 1 erzeugen, die quasi bedeuten, ob du eine Spalte für die Summenbildung verwendest oder nicht.

Beispiel:

Code:

for I = 0:15, disp(bitget(I, 1:4)), end

Funktion ohne Link?

Was ist in deinem Code eigtl. "Summe"?

Grüße,
Harald

ripper1986

Themenstarter

Forum-Anfänger


	Beiträge: 14

	Anmeldedatum: 05.02.13

	Wohnort: ---

	Version: ---

Verfasst am: 10.02.2013, 21:04 Titel:

Hallo,

im Prinzip hat Jan das schon gut erkannt was meine Summe ist, ich habe es jetzt alles ersetzt durch

Code:

sum(A(b, :))

Funktion ohne Link?

das ist viel kürzer ist macht das gleiche Wink

. Ich denke die bitget funktion wird mir helfen. Ich werde es mal versuchen und mich dann wieder melden!

Gruß


Einstellungen und Berechtigungen
Beiträge der letzten Zeit anzeigen:	Du kannst Beiträge in dieses Forum schreiben. Du kannst auf Beiträge in diesem Forum antworten. Du kannst deine Beiträge in diesem Forum nicht bearbeiten. Du kannst deine Beiträge in diesem Forum nicht löschen. Du kannst an Umfragen in diesem Forum nicht mitmachen. Du kannst Dateien in diesem Forum posten Du kannst Dateien in diesem Forum herunterladen

Impressum | Nutzungsbedingungen | Datenschutz | FAQ |

RSS

Hosted by:

Copyright © 2007 - 2025 goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks

MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.