\documentclass[hyperref={pdfpagelabels=false}]{beamer}
\let\Tiny=\tiny
\usepackage[ngerman]{babel} % Für deutsche Konventionen
\usepackage[T1]{fontenc} % Für Umlaute und Schriftart
\usepackage[latin1]{inputenc} % Für Umlaute und Schriftart
\usepackage{ulem} % Zum Durchstreichen
\usetheme{Goettingen} % Theme
\begin{document}
\begin{frame}
\frametitle{Heuristik}
\framesubtitle{DLS-MC}
\visible<1->{Frage: Was wenn dieser Suchprozess zum Erliegen kommt?}
\pause
\visible<2->{\textbf{Lösung:}}
\begin{itemize}
\item<3->
\only<3>{Starte erneut mit anderem initialen Knoten.}
\only<4>{\sout{Starte erneut mit anderem initialen Knoten.}}
\only<5-6>{Bestrafe Knoten die häufig in der Clique auftachen.\newline}
\visible<6>{$\rightarrow$ \textit{Knotenstrafpunkt}}
\end{itemize}
\end{frame}
\end{document}